/*
 * Copyright (c) 2004-2006 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Gou Pengfei
 *
 * Date: A  April 2011
 */

#include "base/intmath.hh"
#include "base/bitfield.hh"
#include "cpu/edge/pred/global_binary.hh"
#include "cpu/base.hh"

template<class Impl>
GlobalBinary<Impl>::GlobalBinary(DerivEdgeCPUParams *params,
        std::string index_mode)
    : BaseBinaryPredictor<Impl>(params, "Global"),
      globalPredictorSize(params->binaryGlobalPredictorSize),
      globalHistoryBits(params->binaryGlobalHistoryBits),
      globalCtrBits(params->binaryGlobalCtrBits),
      blockShiftAmt(params->blockShiftAmt)
{
    initVars();

    if (index_mode == "Address") {
        globalIndexMode = Address;
    } else if (index_mode == "AddressAndPath") {
        globalIndexMode = AddressAndPath;
    } else if (index_mode == "AddressAndCPath") {
        globalIndexMode = AddressAndCPath;
    } else if (index_mode == "AddressAndHist") {
        globalIndexMode = AddressAndHist;
    } else {
        fatal("Invalid global index mode selected for tournament type"
                " predictor\n");
    }

    if (params->btypeGlobalHysteresisMode == "Symmetric") {
        hysteresisMode = Symmetric;
    } else if (params->btypeGlobalHysteresisMode == "Asymmetric") {
        hysteresisMode = Asymmetric;
    } else {
        fatal("Invalid hysteresis mode selected for tournament type"
                " predictor\n");
    }
}

template<class Impl>
GlobalBinary<Impl>::~GlobalBinary()
{
    DPRINTF(EdgePredUnit,
            "Global predictor destructed!\n");
}

template<class Impl>
void
GlobalBinary<Impl>::initVars()
{
    if (!isPowerOf2(globalPredictorSize)) {
        fatal("Invalid global predictor size!\n");
    }

    /** Setup the array of counters for the global predictor */
    globalCtrs.resize(globalPredictorSize);

    for (int i = 0; i < globalPredictorSize; ++i) {
        globalCtrs[i].hysteresis.setBits(globalCtrBits);
    }

    /** Clear the global history */
    for (int i = 0; i < Impl::MaxThreads ;++i ) {
	globalHistory[i] = 0;
        pathHistoryTable[i].resize(globalHistoryBits, static_cast<Addr>(0));
    }

    globalPredictorMask = floorPow2(globalPredictorSize) - 1;
    /** Setup the global history mask */
    globalHistoryMask = (ULL(0x1) << globalHistoryBits) - 1;

    globalHistoryFile.resize(Impl::MaxInFlightBlockNum);
	
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i) {
	globalHistoryFile[i] = 0;
        pathHistoryFile[i].resize(globalHistoryBits, static_cast<Addr>(0));
    }

    DPRINTF(EdgePredUnit, "Global: size: %i, mask: %#x, "
            "counter size: %i, history length: %i, "
            "history mask: %#x.\n",
            globalPredictorSize, globalPredictorMask, 
            globalCtrBits, globalHistoryBits, globalHistoryMask);

    threshold = (ULL(0x1) << (globalCtrBits - 1)) - 1;
    threshold = threshold / 2;
}

template<class Impl>
void
GlobalBinary<Impl>::reset()
{
    for (int i = 0; i < globalPredictorSize; ++i) {
        globalCtrs[i].hysteresis.reset();
    }
	
    //Clear the global history
    for (int i = 0; i < Impl::MaxThreads ;++i) {
	globalHistory[i] = 0;

        for (int j = 0; j < globalHistoryBits; j++) {
            pathHistoryTable[i][j] = 0;
        }
    }
	
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i) {
	globalHistoryFile[i] = 0;

        for (int j = 0; j < globalHistoryBits; j++) {
            pathHistoryFile[i][j] = 0;
        }
    }
}

template<class Impl>
inline
uint64_t
GlobalBinary<Impl>::calcGloPredIdx(Addr block_pc, uint64_t history,
        uint64_t path_hist)
{
    uint64_t index = ULL(0xffffffffffffffff);
    
    if (globalIndexMode == Address) {

        index = (block_pc >> blockShiftAmt) & globalPredictorMask;

    } else if (globalIndexMode == AddressAndPath) {

        index = ((block_pc >> blockShiftAmt) ^
                (path_hist & globalHistoryMask)) & globalPredictorMask;

    } else if (globalIndexMode == AddressAndCPath) {

        uint64_t pattern = bits(path_hist, (globalHistoryBits / 2) - 1, 0);

        index = (((block_pc >> blockShiftAmt) << (globalHistoryBits / 2)) |
            pattern) & globalPredictorMask;

    } else if (globalIndexMode == AddressAndHist) {

        index = (history ^ (block_pc >> blockShiftAmt))
            & globalPredictorMask;

    } else {
        panic("Invalid global index mode selected for tournament type"
                " predictor\n");
    }

    return index;
}

template<class Impl>
bool
GlobalBinary<Impl>::lookup(BlockID block_id, BlockID oldest_block_id, 
        Addr block_pc, ThreadID tid)
{
    uint64_t global_history = 0;
    uint64_t path_history = 0;
    uint64_t global_predictor_idx = 0;

    uint64_t global_history_new = 0;

    //Get global history
    global_history = globalHistory[tid] & globalHistoryMask;
    path_history = getPathHistory(tid);

    global_predictor_idx = calcGloPredIdx(block_pc, global_history,
            path_history);
    
    //Lookup in the global predictor to get its branch prediction
    bool global_prediction = 
        (globalCtrs[global_predictor_idx].hysteresis.read() > threshold);

    DPRINTF(EdgePredUnit,"Global: prediction = %i,"
            " for %#x.\n",
            global_prediction, block_pc);

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1); 

    // Speculative update
    globalHistoryFile[index] = global_history;

    global_history_new = (global_prediction ?
            ((global_history << 1) | (ULL(0x1))) :
            (global_history << 1)) &
            globalHistoryMask;

    globalHistory[tid] = global_history_new;

    PathHistory path = pathHistoryTable[tid];
    pathHistoryFile[index] = pathHistoryTable[tid];
    updatePathHistory(path, block_pc);
    pathHistoryTable[tid] = path;

    return global_prediction;
}

template<class Impl>
bool
GlobalBinary<Impl>::update(BlockID block_id, Addr block_pc, 
        ThreadID tid, bool prediction, bool mispredicted)
{
    uint64_t global_predictor_hist = 0;
    uint64_t path_hist = 0;
    uint64_t global_predictor_idx = 0;

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum -1);

    global_predictor_hist = globalHistoryFile[index];
    path_hist = getPathHistory(block_id, tid);
        
    global_predictor_idx = calcGloPredIdx(block_pc, global_predictor_hist,
            path_hist);

    bool old_pred = 
        (globalCtrs[global_predictor_idx].hysteresis.read() > threshold);

    updateHysteresis(globalCtrs[global_predictor_idx], prediction);

    DPRINTF(EdgePredUnit,"Global: actual = %i, old pred = %i.\n",
            prediction,
            old_pred
           );

    return old_pred;
}

template<class Impl>
void
GlobalBinary<Impl>::squash(Addr block_pc, BlockID block_id, 
        bool prediction, ThreadID tid)
{
    uint64_t global_history = 0;
    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1) ;

    // Restore global history to state prior to this branch.
    global_history = globalHistoryFile[index];
    globalHistory[tid] = (prediction ? ((global_history << 1) | (ULL(0x1))) :
            (global_history << 1)) & globalHistoryMask;

    PathHistory path = pathHistoryFile[index];
    updatePathHistory(path, block_pc);
    pathHistoryTable[tid] = path;

    DPRINTF(EdgePredUnit,"Global: Squashing BP to Block [bid:%i]"
            " due to misprediction.\n",
            block_id);
}

template<class Impl>
void
GlobalBinary<Impl>::squash(BlockID block_id, ThreadID tid)
{
    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1);
    uint64_t global_history = 0;

    global_history = globalHistoryFile[index];
    globalHistory[tid] = global_history;
    pathHistoryTable[tid] = pathHistoryFile[index];

    DPRINTF(EdgePredUnit,"Global: Squashing BP to Block [bid:%i]"
            " due to fault.\n",
            block_id);
}

template<class Impl>
void 
GlobalBinary<Impl>::updatePathHistory(PathHistory &path_history, Addr new_pc)
{
    DPRINTF(EdgePredUnit, "Update path history,"
            " Pop: %#x; Push: %#x\n",
            path_history.back(),
            new_pc);

    path_history.pop_back();

    new_pc >>= blockShiftAmt;

    path_history.push_front(new_pc);
}

template<class Impl>
uint64_t
GlobalBinary<Impl>::getPathHistory(BlockID block_id, ThreadID tid)
{
    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);

    PathHistory path = pathHistoryFile[speculative_frame];
    uint64_t path_hist = 0;

    for (int i = 0; i < path.size(); i++) {
        if (i < 16) {
            // Take 4 bits from each path address
            path_hist |= ((path[i] & ULL(0xF)) << (i * 4));
        }
    }

    return path_hist;
}

template<class Impl>
uint64_t
GlobalBinary<Impl>::getPathHistory(ThreadID tid)
{
    PathHistory path = pathHistoryTable[tid];
    uint64_t path_hist = 0;

    for (int i = 0; i < path.size(); i++) {
        if (i < 16) {
            // Take 4 bits from each path address
            path_hist |= ((path[i] & ULL(0xF)) << (i * 4));
        }
    }

    return path_hist;
}

template<class Impl>
void
GlobalBinary<Impl>::updateHysteresis(PredictionTableEntry &entry,
        bool prediction)
{
    if (hysteresisMode == Symmetric) {
        if (prediction) {
            entry.hysteresis.increment();
        } else {
            entry.hysteresis.decrement();
        }
    } else if (hysteresisMode == Asymmetric) {
        panic("Unimplemented asymmetric hysteresis.\n");
    } else {
        panic("Invalid hysteresis mode selected.\n");
    }
}

